P2831 愤怒的小鸟

首先,我们得知道过原点与两点的抛物线解析式:

设该函数解析式为 y=ax2+bx+c(a<0)y=ax^2+bx+c(a < 0)且过 (0,0),(x1,y1),(x2,y2)(0,0),(x_1,y_1),(x_2,y_2) 三点。

由函数过 (0,0)(0,0)c=0c=0

阅读全文 »

P4778 Counting swaps

对于每个位置 ii , 我们向 pip_i 连一条边。 结合题意可知,一个合法的排列,是一个由 nn 个自环组成的图。

但现在会形成多个环,不妨记环的数量为 kk , 第 ii 个环的大小为 sis_i(包括自环)。

我们现在要做的,就是将这 kk 个环拆成 nn 个自环。

阅读全文 »

SP694 DISUBSTR - Distinct Substrings

这道题用后缀自动机可以暴力解决。

建好后缀自动机后 , 因为起点到后缀自动机上的每一个点都是一个本质不同的子串 , 我们就可以在 DAWG\text{DAWG}dpdpdp[u]dp[u]表示包含转移uu的子串数量,很容易列出转移式:

dp[u]=vson[u]dp[v]dp[u]=\sum_{v \in son[u]} dp[v]

阅读全文 »

SP1811 LCS - Longest Common Substring

一道后缀自动机的板题。

我们从根结点开始匹配,如果有转移就将cnt++cnt++

不然就顺着后缀链接向上跳,直到找到有转移的点,用 MaxlenMaxlen 继续匹配。(后缀链接一定是它的子串,也能被匹配)。

阅读全文 »

SP1812 LCS2 - Longest Common Substring II

我们可以思考一下如何用SAM\text{SAM}求两个串的最长公共子串点这里

多个字符串匹配也很简单,对于每个节点记录每个字符串能匹配的最大值的最小值。

求最大值就是求两个串的最长公共子串,只不过需要给父节点更新,每次取最小值就得到答案。

阅读全文 »

P2408 不同子串个数

这道题用后缀自动机可以暴力解决。

建好后缀自动机后 , 因为起点到后缀自动机上的每一个点都是一个本质不同的子串 , 我们就可以在 DAWG\text{DAWG}dpdpdp[u]dp[u]表示包含转移uu的子串数量,很容易列出转移式:

dp[u]=vson[u]dp[v]dp[u]=\sum_{v \in son[u]} dp[v]

阅读全文 »

SP8222 NSUBSTR - Substrings

不难发现到f[i]f[i]就是长度为 ii 子串的 endpos|endpos| 的最大值。

根据一个性质后缀自动机的一个点的 endposendpos 被他的后继分为了很多部分,所以我们可以用parent树dp\text{parent树dp},处理出它的endpos|endpos|

接着是统计答案,显然我们可以用线段树覆盖。

阅读全文 »

P3195 [HNOI2008]玩具装箱TOY

这道题像我这样的 dpdp 蒟蒻都能一眼看出 dpdp 式:

sumsumcc 的前缀和,则有

dp[i]=min{dp[j]+((ij1)+(sum[i]sum[j])L)2}  (0j<i)dp[i]=min\{ dp[j]+((i-j-1)+(sum[i]-sum[j])-L)^2 \} ~~ (0 \le j < i)

阅读全文 »